package self.learn.record.arlgorithm;

import java.util.Arrays;

/**
 * @author Mercy
 * @date 2018/3/15
 */
public class SortArlgo {
    public static void main(String[] args) {
        int[] arr = {21,5, 4, 1, 2, 7, 9, 8, 3, 6, 10, 11, 2};
//        sort(arr);
//        System.out.println(Arrays.toString(arr));
        devide(arr, 0, arr.length / 2, arr.length);
    }

    /**
     * 希尔排序 针对有序序列在插入时采用交换法
     * @param arr
     */
    public static void sort(int[] arr) {
        //增量gap，并逐步缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            System.out.println(gap);
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (int i = gap; i < arr.length; i++) {

                int j = i;
                int tmp = arr[j];
                while (j - gap >= 0 && tmp < arr[j - gap]) {
                    System.out.println(i);
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = tmp;
            }
        }
    }


    public static int[] cutArr(int[] arr, int low, int up) {
        int[] a = new int[up - low];
        int i = 0;
        for (int x = low; x < up; x++) {

            a[i++] = arr[x];
        }
        return a;
    }

    public static void devide(int[] arr, int low, int middle, int high) {
        System.out.println("low=" + low + ",middle=" + middle + ",high=" + high);

        if (low < middle) {
            int[] tmpArr1 = cutArr(arr, low, middle);
            devide(tmpArr1, 0, tmpArr1.length / 2, tmpArr1.length);

            int[] tmpArr2 = cutArr(arr, middle, high);
            devide(tmpArr2, 0, (high - middle) / 2, tmpArr2.length);


            System.out.println("tmpArr1:" + Arrays.toString(tmpArr1) + "tmpArr2:" + Arrays.toString(tmpArr2));

            arr = sortDevide(tmpArr1, tmpArr2);
            System.out.println("arr:" + Arrays.toString(arr));
        }
    }

    public static int[] sortDevide(int[] a1, int[] a2) {
        int[] a3 = new int[a1.length + a2.length];
        int j = 0, k = 0, q = Math.min(a1.length, a2.length);

        for (int i = 0; i < a3.length; i++) {

            a3[i] = (j >= a1.length) ? a2[k++] :
                    ((k >= a2.length) ? a1[j++] :
                            ((a1[j] < a2[k]) ? a1[j++] : a2[k++]));
        }
        System.out.println(Arrays.toString(a3));
        return a3;

    }
}
